import java.util.Stack;

public class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
}

class Solution {
    //解法1：反转链表，然后遍历，存入数组
    public int[] reversePrint1(ListNode head) {
        int [] arr = new int[0];
        if (head == null) return arr;
        int size = 0;
        ListNode cur = head.next;
        while (cur != null) {
            ListNode curNext = cur.next;
            cur.next = head;
            head = cur;
            cur = curNext;
            size++;
        }
        arr = new int[size + 1];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = head.val;
            head = head.next;
        }
        return arr;
    }
    //解法2：遍历链表，获取链表长度，根据链表长度创建数组，数组从后往前放链表元素，比解法一优化了内存
    public static int[] reversePrint2(ListNode head) {
        ListNode node = head;
        int count = 0;
        while (node != null) {
            ++count;
            node = node.next;
        }
        int[] nums = new int[count];
        node = head;
        for (int i = count - 1; i >= 0; --i) {
            nums[i] = node.val;
            node = node.next;
        }
        return nums;
    }
    //解法3：利用辅助栈，遍历链表，将结点依次放入栈中，依次出栈，并用数组存储节点元素 （速度不如 1 2 快）
    public int[] reversePrint3(ListNode head) {
        Stack<ListNode> stack = new Stack<ListNode>();
        ListNode temp = head;
        while (temp != null) {
            stack.push(temp);
            temp = temp.next;
        }
        int size = stack.size();
        int[] print = new int[size];
        for (int i = 0; i < size; i++) {
            print[i] = stack.pop().val;
        }
        return print;
    }

}
